Crate slotmap

source ·
Expand description

slotmap

This library provides a container with persistent unique keys to access stored values, SlotMap. Upon insertion a key is returned that can be used to later access or remove the values. Insertion, removal and access all take O(1) time with low overhead. Great for storing collections of objects that need stable, safe references but have no clear ownership otherwise, such as game entities or graph nodes.

The difference between a BTreeMap or HashMap and a slot map is that the slot map generates and returns the key when inserting a value. A key is always unique and will only refer to the value that was inserted. A slot map’s main purpose is to simply own things in a safe and efficient manner.

You can also create (multiple) secondary maps that can map the keys returned by SlotMap to other values, to associate arbitrary data with objects stored in slot maps, without hashing required - it’s direct indexing under the hood.

The minimum required stable Rust version for this crate is 1.49.

Examples

let mut sm = SlotMap::new();
let foo = sm.insert("foo");  // Key generated on insert.
let bar = sm.insert("bar");
assert_eq!(sm[foo], "foo");
assert_eq!(sm[bar], "bar");

sm.remove(bar);
let reuse = sm.insert("reuse");  // Space from bar reused.
assert_eq!(sm.contains_key(bar), false);  // After deletion a key stays invalid.

let mut sec = SecondaryMap::new();
sec.insert(foo, "noun");  // We provide the key for secondary maps.
sec.insert(reuse, "verb");

for (key, val) in sm {
    println!("{} is a {}", val, sec[key]);
}

Serialization through serde, no_std support and unstable features

Both keys and the slot maps have full (de)seralization support through the serde library. A key remains valid for a slot map even after one or both have been serialized and deserialized! This makes storing or transferring complicated referential structures and graphs a breeze. Care has been taken such that deserializing keys and slot maps from untrusted sources is safe. If you wish to use these features you must enable the serde feature flag for slotmap in your Cargo.toml.

slotmap = { version = "1.0", features = ["serde"] }

This crate also supports no_std environments, but does require the alloc crate to be available. To enable this you have to disable the std feature that is enabled by default:

slotmap = { version = "1.0", default-features = false }

Unfortunately SparseSecondaryMap is not available in no_std, because it relies on HashMap. Finally the unstable feature can be defined to enable the parts of slotmap that only work on nightly Rust.

Why not index a Vec, or use slab, stable-vec, etc?

Those solutions either can not reclaim memory from deleted elements or suffer from the ABA problem. The keys returned by slotmap are versioned. This means that once a key is removed, it stays removed, even if the physical storage inside the slotmap is reused for new elements. The key is a permanently unique* reference to the inserted value. Despite supporting versioning, a SlotMap is often not (much) slower than the alternative, by internally using carefully checked unsafe code. Finally, slotmap simply has a lot of features that make your life easy.

Performance characteristics and implementation details

Insertion, access and deletion is all O(1) with low overhead by storing the elements inside a Vec. Unlike references or indices into a vector, unless you remove a key it is never invalidated. Behind the scenes each slot in the vector is a (value, version) tuple. After insertion the returned key also contains a version. Only when the stored version and version in a key match is a key valid. This allows us to reuse space in the vector after deletion without letting removed keys point to spurious new elements. *After 231 deletions and insertions to the same underlying slot the version wraps around and such a spurious reference could potentially occur. It is incredibly unlikely however, and in all circumstances is the behavior safe. A slot map can hold up to 232 - 2 elements at a time.

The memory usage for each slot in SlotMap is 4 + max(sizeof(T), 4) rounded up to the alignment of T. Similarly it is 4 + max(sizeof(T), 12) for HopSlotMap. DenseSlotMap has an overhead of 8 bytes per element and 8 bytes per slot.

Choosing SlotMap, HopSlotMap or DenseSlotMap

A SlotMap is the fastest for most operations, except iteration. It can never shrink the size of its underlying storage, because it must remember for each storage slot what the latest stored version was, even if the slot is empty now. This means that iteration can be slow as it must iterate over potentially a lot of empty slots.

HopSlotMap solves this by maintaining more information on insertion/removal, allowing it to iterate only over filled slots by ‘hopping over’ contiguous blocks of vacant slots. This can give it significantly better iteration speed. If you expect to iterate over all elements in a SlotMap a lot, and potentially have a lot of deleted elements, choose HopSlotMap. The downside is that insertion and removal is roughly twice as slow. Random access is the same speed for both.

DenseSlotMap goes even further and stores all elements on a contiguous block of memory. It uses two indirections per random access; the slots contain indices used to access the contiguous memory. This means random access is slower than both SlotMap and HopSlotMap, but iteration is significantly faster, as fast as a normal Vec.

Choosing SecondaryMap or SparseSecondaryMap

You want to associate extra data with objects stored in a slot map, so you use (multiple) secondary maps to map keys to that data.

A SecondaryMap is simply a Vec of slots like slot map is, and essentially provides all the same guarantees as SlotMap does for its operations (with the exception that you provide the keys as produced by the primary slot map). This does mean that even if you associate data to only a single element from the primary slot map, you could need and have to initialize as much memory as the original.

A SparseSecondaryMap is like a HashMap from keys to objects, however it automatically removes outdated keys for slots that had their space reused. You should use this variant if you expect to store some associated data for only a small portion of the primary slot map.

Custom key types

If you have multiple slot maps it’s an error to use the key of one slot map on another slot map. The result is safe, but unspecified, and can not be detected at runtime, so it can lead to a hard to find bug.

To prevent this, slot maps allow you to specify what the type is of the key they return. You can construct new key types using the new_key_type! macro. The resulting type behaves exactly like DefaultKey, but is a distinct type. So instead of simply using SlotMap<DefaultKey, Player> you would use:

new_key_type! { struct PlayerKey; }
let sm: SlotMap<PlayerKey, Player> = SlotMap::with_key();

You can write code generic over any key type using the Key trait.

Modules

  • basic
    Contains the slot map implementation.
  • dense
    Contains the dense slot map implementation.
  • hop
    Contains the faster iteration, slower insertion/removal slot map implementation.
  • secondary
    Contains the secondary map implementation.
  • sparse_secondary
    Contains the sparse secondary map implementation.

Macros

  • new_key_type
    A helper macro to create new key types. If you use a new key type for each slot map you create you can entirely prevent using the wrong key on the wrong slot map.

Structs

  • DefaultKey
    The default slot map key type.
  • DenseSlotMap
    Dense slot map, storage with stable unique keys.
  • HopSlotMap
    Hop slot map, storage with stable unique keys.
  • KeyData
    The actual data stored in a Key.
  • SecondaryMap
    Secondary map, associate data with previously stored elements in a slot map.
  • SlotMap
    Slot map, storage with stable unique keys.
  • SparseSecondaryMap
    Sparse secondary map, associate data with previously stored elements in a slot map.

Traits

  • Key
    Key used to access stored values in a slot map.